package com.xinpan.exercise;


public class DistinctSubSeq {
    public int numDistinct(String S, String T) {
        // Start typing your Java solution below
        // DO NOT write main() function
        if(S == null || T == null || T.length() > S.length())
            return 0;
        
        int[][] his = new int[T.length()+1][S.length()+1];
        for(int i = 0; i < T.length()+1; i++)
            his[i][0] = 0;
        for(int j = 0; j < S.length()+1; j++)
            his[0][j] = 1;
            
        for(int i = 0; i < T.length(); i++)
        {
            for(int j = 0; j < S.length(); j++)
            {
                if(T.charAt(i) == S.charAt(j))
                    his[i+1][j+1] = his[i][j] + his[i+1][j];
                else
                    his[i+1][j+1] = his[i+1][j];
            }
        }
        return his[T.length()][S.length()];
    }
    
    public static void main(String[] args)
    {
    	DistinctSubSeq dss = new DistinctSubSeq();
    	int res = dss.numDistinct("b", "a");
    	System.out.println(res);
    }
	/*
    public int numDistinct(String S, String T) {
        // Start typing your Java solution below
        // DO NOT write main() function
        if(S == null || T == null || T.length() > S.length())
            return 0;
            
        int sum = 0;
        for(int i = 0; i < S.length(); i++)
        {
            if(S.length() - i < T.length())
                return sum;
                
            if(S.charAt(i) == T.charAt(0))
                sum += subSeq(S, T, i+1, 1);
        }
        return sum;
    }
    
    public int subSeq(String s, String t, int sp, int tp)
    {
    	Map<Character, List<Integer>> l = new HashMap<Character, List<Integer>>();
    	
        if(tp == t.length())
            return 1;
        
        PriorityQueue<Integer> sl = new PriorityQueue<Integer>();
        sl.
        int sum = 0;
        for(int i = sp; i < s.length(); i++)
        {
            if(s.length() - i < t.length() - tp)
                return sum;
            if(s.charAt(i) == t.charAt(tp))
                sum += subSeq(s, t, i+1, tp+1);
        }
        
        return sum;
    }*/
}
